/*
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

[3,9,20,null,null,15,7]

[
  [3],
  [9,20],
  [15,7]
]
------------------------------------------------------------------
*/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

 //用一个队列来输出每一层的节点，在用一个二维数组来记录每一层的节点
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    if(root == NULL){
        (*returnSize)= 0;
        return root;
    }

    struct TreeNode* queue[1010];
    int front = 0, rear = 0, i = 0, j = 0, count = 0, k = 1;
    struct TreeNode* p = NULL;
    int** array = (int**)malloc(sizeof(int*)*1010);//申请一个指针数组(二维数组)
    *returnColumnSizes = (int*)malloc(sizeof(int)*1010);//申请一个int型数组
    queue[rear++] = root;//入队列
    array[i] = (int*)malloc(sizeof(int)*k);//用指针数组的第一个指针指向树第一层的数组
    (*returnColumnSizes)[i] = k;//第一层数组的长度
    while(front < rear){
        p = queue[front++];//出队列并用指针p指向该节点
        array[i][j++] = p->val;//二维数组第i层第j个元素记录该节点的值
        if(p->left){//查看左孩子，有则入队
            queue[rear++] = p->left;
            count++;//记录下一层节点数
        }
        if(p->right){//查看右孩子，有则入队
            queue[rear++] = p->right;
            count++;
        }
        k--;//改层已经记录一个节点值，若k==0,则说明该层的节点已经记录完，用k=count,来更新下一层节点数
        if(k == 0){
            k = count;
            count = 0;
            j = 0;//从当前i层第一个节点开始，所以对应当前二维数组第i行第一个元素
            i++;//到下一层，也到下一行
            array[i] = (int*)malloc(sizeof(int)*k);//重新分配下一层对应节点的数组大小
            (*returnColumnSizes)[i] = k;//返回下一层节点个数
        }
    }
        *returnSize = i;
    return array;
}


